/**
 * 
 */
package com.gwcloud.leetcode.tags.tree;

import com.gwcloud.leetcode.common.datastructure.TreeNode;

/**
 * @ClassName   : Leetcode124 
 * @author      : ganwei 
 * @date        : 2020年5月5日
 * @Description : Leetcode124 二叉树中的最大路径和
 */
public class Leetcode0124 {
    private int ans = Integer.MIN_VALUE;
	/**
     * -解题思路，树的后序遍历
     */
	public int maxPathSum(TreeNode root) {
    	oneSideMax(root);
    	return ans;
    }
	public int oneSideMax(TreeNode root){
		if(root == null){
			return 0;
		}
		int left = Math.max(0, oneSideMax(root.left));
		int right = Math.max(0, oneSideMax(root.right));
		ans = Math.max(ans, root.val+left+right);
		return Math.max(left, right) + root.val;
		
	}
	
	public static void main(String[] args){
		Leetcode0124 l124 = new Leetcode0124();
		TreeNode t1 = new TreeNode(-10);
		TreeNode t2 = new TreeNode(9);
		TreeNode t3 = new TreeNode(20);
		TreeNode t4 = new TreeNode(15);
		TreeNode t5 = new TreeNode(7);
		t1.left = t2;
		t1.right = t3;
		t3.left = t4;
		t3.right = t5;
		System.out.println(l124.maxPathSum(t1));
	}
}
